package structure;

import bean.linklist.Node;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

public class StructureTest {

    private static char c = 'A';
    private static int i = 0;

    public static void main(String[] args) {
        Runnable runnable = new Runnable() {
            public void run() {
                synchronized (this) {    //加锁
                    try {
                        System.out.println("name--" + Thread.currentThread().getName());
                        int threadId = Integer.parseInt(Thread.currentThread().getName());
                        System.out.println("threadId--" + threadId);
                        while (i < 26) {
                            if (i % 3 == threadId - 1) {
                                System.out.println(threadId + "" + (char) c++);
                                i++;
                                notifyAll();// 唤醒处于等待状态的线程
                            } else {
                                wait(); //释放当前锁并进入等待状态
                            }
                        }
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }//执行结束释放当前锁
            }
        };
        Thread t1 = new Thread(runnable, "1");
        Thread t2 = new Thread(runnable, "2");
        Thread t3 = new Thread(runnable, "3");
        t1.start();
        t2.start();
        t3.start();
    }

    char c1 = 'A';

    int n = 0;

    /**
     * 用三个线程，顺序打印字母A～Z，输出结果是1A，2B，3C，1D，2E。。。
     * 技术点：线程同步
     * 思路：加锁进行限制，并配合wait()和notifyAll()
     */
    @Test
    public void testOutPrintChar() {
        Runnable runnable = new Runnable() {
            @Override
            public void run() {
                synchronized (this) {
                    int threadId = Integer.parseInt(Thread.currentThread().getName());
                    while (n < 26) {
                        try {
                            if (n % 3 == threadId - 1) {//n%3:1、2  threadId-1:1,2
                                System.out.println(threadId + "" + (char) c1++);
                                n++;
                                notifyAll();
                            } else {
                                wait();
                            }
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }
            }
        };
        Thread thread1 = new Thread(runnable, "1");
        Thread thread2 = new Thread(runnable, "2");
        Thread thread3 = new Thread(runnable, "3");
        thread1.start();
        thread2.start();
        thread3.start();

    }

    /**
     * 使用两个栈实现一个队列的效果
     */
    @Test
    public void stack2Queue() {
        Stack<Integer> stack1 = new Stack<>();
        stack1.push(1);
        stack1.push(2);
        stack1.push(3);
        stack1.push(4);
        Stack<Integer> stack2 = new Stack<>();
        if (stack2.empty()) {
            while (!stack1.empty()) {
                Integer pop = stack1.pop();
                System.out.println("stack1--" + pop);
                stack2.push(pop);
            }
        }
        while (!stack2.empty()) {
            System.out.println("stack2--" + stack2.pop());
        }
//        return stack2.pop();
    }

    public static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode reverstLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode p = new ListNode(-1);
        p.next = head;
        ListNode nextNode = head.next;
        while (nextNode != null) {
            head.next = nextNode.next;
            nextNode.next = p.next;
            p.next = nextNode;
            nextNode = head.next;
        }
        return p.next;
    }

    /**
     * 递归法 翻转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseLinkedList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 1,2,3,4
        ListNode pNode = reverseLinkedList1(head.next);
        head.next.next = head;
        head.next = null;

        return pNode;

    }

    @Test
    public void testReverseListNode() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode result = reverseLinkedList1(node1);
        ListNode node = result;
        while (node != null) {
            System.out.println("" + node.val);
            node = node.next;
        }
    }

    /**
     * 二分查找法
     *
     * @param arr
     * @param key
     * @return
     */
    public int binarySearch(int arr[], int key) {

        int low, mid, hight;
        low = 0;
        hight = arr.length - 1;
        while (low <= hight) {
            mid = (low + hight) / 2;
            if (arr[mid] > key) {
                hight = mid - 1;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    @Test
    public void testBindarySearch() {
        int arr[] = {2, 3, 5, 8, 11, 14, 15, 16, 18, 21, 25};
        int result = binarySearch(arr, 6);
        System.out.println("result:" + result);
    }

    /**
     * 冒泡拍讯算法
     * 时间复杂度 o(N²)
     * 空间复杂度 常量
     *
     * @param arr
     * @return
     */
    private int[] bubbleSort(int arr[]) {
        if (arr == null || arr.length == 1) {
            return arr;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序 时间复杂度o(N²) 空间复杂度 常量
     * 选择排序是最稳定的算法之一，因为无论什么数据进入都是O(N²)
     * 选择排序的原理：首先在未排序的序列中找到最小的元素，存放到排序序列的起始位置，然后再从剩余的未排序的
     * 序列中继续寻找最小的元素，然后放到已排序的序列末尾，以此类推，直到所有的元素均排序完成。
     *
     * @param arr
     * @return
     */
    private int[] selectionSort(int arr[]) {

        if (arr == null || arr.length == 1) {
            return arr;
        }
        for (int i = 0; i < arr.length; i++) {
            int minIndex = 0;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;//从未比较的数据中找到最小的数据
                }
            }

            //取出最小的
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];//当前位置数据和最小值调换位置
            arr[i] = temp;
        }

        return arr;
    }

    /**
     * 插入排序 通过构建有序序列，对于未拍讯的数据，在已经排序的序列中从后向前扫描，找到合适的位置插入
     * 在从后向前扫描的过程中，需要反复把已经排序的元素逐步向后挪动，为新元素腾出空间。
     *
     * @param arr
     * @return
     */
    private int[] insertSort(int arr[]) {

        int j;
        for (int i = 0; i < arr.length - 1; i++) {
            int temp = arr[i + 1];
            for (j = i; j >= 0 && arr[j] > temp; j--) {//在已经排序的列表中对比 比i小的范围就是已经排序的
                arr[j + 1] = arr[j];//向后移动
            }
            arr[j + 1] = temp;
        }

        return arr;
    }

    @Test
    public void testBubbleSort() {


        int arr[] = {36, 31, 15, 8, 11, 14, 19, 22, 18, 21, 25};
//        int relust[] = bubbleSort(arr);//冒泡排序
        int relust[] = selectionSort(arr);//选择排序
//        int relust[] = insertSort(arr);//插入排序

        for (int i1 : relust) {
            System.out.println("result-i-:" + i1);
        }
    }

    private void operation(int arr[][]) {

        int length = arr.length;
        for (int i = 0; i < length; i++) {

            for (int j = 0; j < arr[i].length; j++) {

            }
        }

    }

    @Test
    public void testSpiralOrder() {
        int arrs[][] = {//给定一个二维数组
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        List<Integer> list = spiralOrder(arrs);
        for (int integer : list) {
            System.out.println("result-i-:" + integer);
        }
    }

    /**
     * 螺旋 输出二维数组
     * 原理讲解
     * https://leetcode-cn.com/problems/spiral-matrix/solution/dong-hua-mo-ni-yi-xia-jiu-neng-gao-dong-i27qf/
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> arr = new ArrayList<>();
        int left = 0, right = matrix[0].length - 1;//取出一行的数量
        int top = 0, down = matrix.length - 1;//取出一列的数量

        while (true) {
            for (int i = left; i <= right; ++i) {//从左到右遍历
                arr.add(matrix[top][i]);
            }
            top++;//一行完毕，
            if (top > down) break;
            for (int i = top; i <= down; ++i) {//从数组的最右边一列开始，从上到下遍历，
                arr.add(matrix[i][right]);
            }
            right--;//列数从右到左减一
            if (left > right) break;
            for (int i = right; i >= left; --i) {//从底部由右到左遍历最后一行
                arr.add(matrix[down][i]);
            }
            down--;//最后一行便利完毕 减去
            if (top > down) break;
            for (int i = down; i >= top; --i) {////第一列从下向上遍历，
                arr.add(matrix[i][left]);
            }
            left++;//第一列遍历完毕下一次从第二列开始...
            if (left > right) break;

        }
        return arr;
    }

    @Test
    public void testString() {

        String s1 = "auacr4babardg";
        String s2 = "baba";
        int result1 = strStr(s1, s2);
        int result2 = strStr2(s1, s2);
        System.out.println("result1-:" + result1);
        System.out.println("result2-:" + result2);
    }

    public int strStr(String hayStack, String needle) {
        int hayLength = hayStack.length();
        int needleLength = needle.length();
        if (hayLength < needleLength) {
            return -1;
        }
        if (needleLength == 0) {
            return 0;
        }

        for (int i = 0; i < hayLength; i++) {
            int j;
            for (j = 0; j < needleLength; j++) {
                if (hayStack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == needleLength) {
                return i;
            }
        }
        return -1;
    }

    private int strStr2(String hayStack, String needle) {
        int hayLength = hayStack.length();
        int needleLength = needle.length();
        if (hayLength < needleLength) {
            return -1;
        }
        if (needleLength == 0) {
            return 0;
        }
        int i, j;

        for (i = 0, j = 0; i < hayLength && j < needleLength; i++) {
            if (hayStack.charAt(i) == needle.charAt(j)) {
                j++;
            } else {
                i -= j;
                j = 0;
            }
        }

        int result = j == needleLength ? i - needleLength : -1;

        return result;
    }

    @Test
    public void testListNode() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node2;
        boolean isCycle = hasCycle(node1);
        System.out.println("isCycle--" + isCycle);
    }

    private boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            if (fast == low) {
                return true;
            }
        }
        return false;
    }

    @Test
    public void testFindNodeInList() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
//        ListNode node8 = new ListNode(8);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
//        node7.next = node8;
        //找到链表的倒数第n个节点
//        ListNode node = findNodeInList(node1, 3);
//        System.out.println(node.val);

        System.out.println("-------------------------------------------------------");

        //找到链表的中间节点
        ListNode middleNode = findMiddleNode(node1);
        System.out.println(middleNode.val);

    }

    /**
     * 找出链表中的倒数第n个元素
     * <p>
     * 思路1：把链表的元素放到数组中，通过下标访问
     * 思路2：通过双指针的方式访问，查找倒数第n个元素，先让一个指针移动n-1个节点，这时候第二个指针和第一个指针同时移动，当头一个
     *
     * @param head
     * @return
     */
    private ListNode findNodeInList(ListNode head, int n) {
        if (head == null && head.next == null) {
            return head;
        }
        ListNode proNode = head;
        ListNode lastNode = head;
        for (int i = 0; i < n; i++) {
            proNode = proNode.next;
        }
        while (proNode.next != null) {
            proNode = proNode.next;
            lastNode = lastNode.next;
        }
        return lastNode;
    }

    /**
     * 寻找一个链表的中间节点
     * 思路1：通过链表遍历把链表装入数组中，通过拿到数组的长度获取中间节点
     * 思路2：通过快慢指针 设置快指针是慢指针的2倍速度，当快指针走到末尾时慢指针刚好指向中间节点
     *
     * @param head
     * @return
     */
    private ListNode findMiddleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
        }
        return slowNode;
    }

    @Test
    public void testFindCommonNodeInList() {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);

        node1.next = node3;
        node3.next = node5;
        node5.next = node7;

        node2.next = node4;
        node4.next = node6;
        node6.next = node7;

        node7.next = node8;

        ListNode result = findCommonNodeInList(node1, node2);
        System.out.println("result--" + result.val);
    }

    /**
     * 找到两个链表的公共节点
     * 思路1：采用HashSet存储一个链表的节点，然后遍历第二个链表，判断是否存在相同的节点，有责返回。
     * 思路2：采用双指针策略，分别让两个指针指向两个链表的开始，顺序遍历，当两个链表第一次遍历完毕后，交换两个指针，然后再一次遍历；
     * 由于每个指针都遍历了到了两个链表，节点数相同，因此在第二次的时候会在公共节点相遇，由此则找到了公共节点
     *
     * @param headA
     * @param headB
     * @return
     */
    private ListNode findCommonNodeInList(ListNode headA, ListNode headB) {

        // 创建节点指针分别指向参数headA，headB，在对tempA、tempB操作的过程 原生的节点headA、headB一直没有变化
        ListNode tempA = headA;
        ListNode tempB = headB;

        //思路1：使用set来过滤重复数据
//        HashSet<ListNode> hashSet = new HashSet<>();
//        while (tempA != null) {
//            hashSet.add(tempA);
//            tempA = tempA.next;
//        }
//        while (tempB != null) {
//            if (hashSet.contains(tempB)) {
//                return tempB;
//            }
//            tempB = tempB.next;
//        }
        //思路2：使用双指针
        while (tempA != tempB) {
            tempA = tempA != null ? tempA.next : headA;
            tempB = tempB != null ? tempB.next : headB;
        }

        return tempA;
    }

    @Test
    public void testChangeNumber() {
        int num = 80;
        System.out.println("num1-" + num);
        changeNumber(num);
        System.out.println("num2-" + num);

        System.out.println("---------------------------------------------------");

        ListNode node = new ListNode(20);
        System.out.println("node1-" + node.val + "--node--" + node);
        changeObject(node);
        System.out.println("node2-" + node.val + "--node--" + node);

    }

    /**
     * 改变对象（传递引用）
     *
     * @param node
     */
    private void changeObject(ListNode node) {
        node.val = 123;// 给参数引用的对象修改val值，这个修改会在引用地址指向的实参对象中改变，最后输出发生变化
        System.out.println("changeObject1-" + node.val + "--node--" + node);
        node = new ListNode(66); //重新赋值一个对象,这个对象并不会改变参数引用node指向的对象
        System.out.println("changeObject2-" + node.val + "--node--" + node);
    }

    private void changeNumber(int a) {
        a = 123;
        System.out.println("changeNumber--" + a);
    }

}
